#include<iostream>
#include<cstring>
#include<queue>
#include<omp.h>
#include<sys/time.h>
using namespace std;
const int N = 10000, M = N*N;
int h[N], e[M], ne[M], w[M], idx;
int q[N], head, tail = -1;
int thread_count=7;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<int, int> PII;
int st[N], dist[N];
int m_dist[N][8];
int book[N];
void SPFA(int n) {
	q[++tail] = 1;
	dist[1] = 0;
	st[1] = 1;
	while (head <= tail) {
		int cur_head = head, cur_tail = tail;
#pragma omp parallel num_threads(thread_count)
		{
#pragma omp for
			for (int k = cur_head; k <= cur_tail; ++k) 
			{
				int t = q[k],id=omp_get_thread_num();
				for (int i = h[t]; ~i; i = ne[i]) {
					int j = e[i];
					if (dist[j] > dist[t] + w[i]) {
						m_dist[j][id] = min(dist[t] + w[i],m_dist[j][id]);
						book[j] = 1;
						if (!st[j]) {
#pragma omp critical
							q[++tail] = j;
							st[j] = 1;
						}
					}
				}
				head = cur_tail + 1;
			}
#pragma omp for 
			for(int i=1;i<n;++i)
				if (book[i]) {
					book[i] = 0;
					for (int j = 0; j < thread_count; ++j)
						dist[i] = min(dist[i], m_dist[i][j]);
				}
		}
	}
	for (int i = 1; i <= n; ++i)
		if (dist[i] >= 0x3f3f3f3f / 2)
			dist[i] = -1;
}
int main(int argc,char** args) {
	memset(dist, 0x3f, sizeof dist);
	memset(h, -1, sizeof h);
	memset(m_dist, 0x3f, sizeof m_dist);
	int n, m;
	cin >> n >> m;
	thread_count=args[1][0]-'0';
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		add(a, b, c);
	}
	
	
    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	SPFA(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}